{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Next Permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nextPermutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下一个排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>整数数组的一个 <strong>排列</strong>&nbsp; 就是将其所有成员以序列或线性顺序排列。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>arr = [1,2,3]</code> ，以下这些都可以视作 <code>arr</code> 的排列：<code>[1,2,3]</code>、<code>[1,3,2]</code>、<code>[3,1,2]</code>、<code>[2,3,1]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>整数数组的 <strong>下一个排列</strong> 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 <strong>下一个排列</strong> 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>arr = [1,2,3]</code> 的下一个排列是 <code>[1,3,2]</code> 。</li>\n",
    "\t<li>类似地，<code>arr = [2,3,1]</code> 的下一个排列是 <code>[3,1,2]</code> 。</li>\n",
    "\t<li>而 <code>arr = [3,2,1]</code> 的下一个排列是 <code>[1,2,3]</code> ，因为 <code>[3,2,1]</code> 不存在一个字典序更大的排列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数数组 <code>nums</code> ，找出 <code>nums</code> 的下一个排列。</p>\n",
    "\n",
    "<p>必须<strong><a href=\"https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95\" target=\"_blank\"> 原地 </a></strong>修改，只允许使用额外常数空间。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>[1,3,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,1]\n",
    "<strong>输出：</strong>[1,2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,5]\n",
    "<strong>输出：</strong>[1,5,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [next-permutation](https://leetcode.cn/problems/next-permutation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [next-permutation](https://leetcode.cn/problems/next-permutation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[3,2,1]', '[1,1,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        \"\"\"\n",
    "        :param num:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def nextPermutation(nums: List[int]) -> None:\n",
    "            i = len(nums) - 2\n",
    "            while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "                i -= 1\n",
    "            if i >= 0:\n",
    "                j = len(nums) - 1\n",
    "                while j >= 0 and nums[i] >= nums[j]:\n",
    "                    j -= 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "\n",
    "            left, right = i + 1, len(nums) - 1\n",
    "            while left < right:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "\n",
    "        left = num[:len(num) // 2]\n",
    "        rigtt_list = [i for i in left]\n",
    "        minval = sorted(rigtt_list)\n",
    "        nextPermutation(rigtt_list)\n",
    "        if minval == rigtt_list:\n",
    "            return ''\n",
    "        ret = rigtt_list\n",
    "        mirror = [i for i in reversed(ret)]\n",
    "        if len(num) % 2 == 0:\n",
    "            ans1 = ''.join(ret) + ''.join(mirror)\n",
    "            return ans1\n",
    "        else:\n",
    "            ans1 = ''.join(ret) + num[len(num) // 2] + ''.join(mirror)\n",
    "            return ans1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.nextPalindrome('23143034132'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextPalindrome(self, num: str) -> str:\n",
    "        \"\"\"\n",
    "\n",
    "        :param num:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        left = num[:len(num) // 2]\n",
    "        rigtt_list = [i for i in left]\n",
    "        minval = sorted(rigtt_list)\n",
    "        self.nextPermutation(rigtt_list)\n",
    "        if minval == rigtt_list:\n",
    "            return ''\n",
    "        ret = rigtt_list\n",
    "        mirror = [i for i in reversed(ret)]\n",
    "        if len(num) % 2 == 0:\n",
    "            ans1 = ''.join(ret) + ''.join(mirror)\n",
    "            return ans1\n",
    "        else:\n",
    "            ans1 = ''.join(ret) + num[len(num) // 2] + ''.join(mirror)\n",
    "            return ans1\n",
    "\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i >= 0:\n",
    "            j = len(nums) - 1\n",
    "            while j >= 0 and nums[i] >= nums[j]:\n",
    "                j -= 1\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "\n",
    "        left, right = i + 1, len(nums) - 1\n",
    "        while left < right:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.nextPalindrome('23143034132'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        # if sorted(nums) == nums[::-1]:\n",
    "        #     nums[:] = sorted(nums)\n",
    "        #     return None\n",
    "        # if len(nums) == 2:\n",
    "        #     nums[:] = nums[::-1]\n",
    "        #     return None\n",
    "        # for i in range(len(nums)-1, 0, -1):\n",
    "        #     for j in range(i-1, -1, -1):\n",
    "        #         if nums[j] <= nums[i]:\n",
    "        #             nums[j], nums[i] = nums[i], nums[j]\n",
    "        #             nums[j+1:] = sorted(nums[j+1:])\n",
    "        #             return None\n",
    "        # find the point where start to drop\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i+1] <= nums[i]:\n",
    "            i -= 1\n",
    "        # find the rightest point which is just larger than the point and swap them\n",
    "        if i >= 0:\n",
    "            j = len(nums) - 1\n",
    "            while j >= 0 and nums[j] <= nums[i]:\n",
    "                j -= 1\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i+1:] = sorted(nums[i+1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef nextPermutation(self, nums):\n",
    "\t\t\"\"\"\n",
    "\t\t:type nums: List[int]\n",
    "\t\t:rtype: void Do not return anything, modify nums in-place instead.\n",
    "\t\t\"\"\"\n",
    "\t\tj=len(nums)-1\n",
    "\t\tk=0\n",
    "\t\twhile j:\n",
    "\t\t\tif nums[j-1]<nums[j]:\n",
    "\t\t\t\tk=1\n",
    "\t\t\t\tn=nums[j:]\n",
    "\t\t\t\ti=0\n",
    "\t\t\t\twhile n[i]>nums[j-1]:\n",
    "\t\t\t\t\ti=i+1\n",
    "\t\t\t\t\tif j+i==len(nums):\n",
    "\t\t\t\t\t\tbreak\n",
    "\t\t\t\tnums[j-1],nums[j+i-1]=nums[j+i-1],nums[j-1] \n",
    "\t\t\t\tn=nums[j:]\n",
    "\t\t\t\tn.sort() \n",
    "\t\t\t\tnums[j:]=n \n",
    "\t\t\t\tbreak\n",
    "\t\t\tj=j-1\n",
    "\t\tif k==0:\n",
    "\t\t\tnums.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: 'List[int]') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        j = n - 1\n",
    "        while j >= 1 and nums[j - 1] >= nums[j]:\n",
    "            j -= 1\n",
    "        if j:\n",
    "            pivot = nums[j - 1]\n",
    "            l, r = j, n - 1\n",
    "            while l <= r:\n",
    "                c = (l + r) // 2\n",
    "                if nums[c] <= pivot:\n",
    "                    r = c - 1\n",
    "                else:\n",
    "                    l = c + 1\n",
    "            nums[j - 1], nums[r] = nums[r], nums[j - 1]\n",
    "        print(nums)\n",
    "        jj, kk = j, n - 1\n",
    "        while jj < kk:\n",
    "            nums[jj], nums[kk] = nums[kk], nums[jj]\n",
    "            jj, kk = jj + 1, kk - 1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if len(nums)>1:\n",
    "            the_loc=self.loc(nums)\n",
    "            print('the_loc',the_loc)\n",
    "            if the_loc == -1:\n",
    "                nums.sort()\n",
    "            else:\n",
    "                j=the_loc+1\n",
    "                found=the_loc\n",
    "                while(j<len(nums)):\n",
    "                    if nums[j]>nums[the_loc-1] and nums[j]<=nums[found]:\n",
    "                        found=j\n",
    "                    j+=1\n",
    "                print('found:',found)\n",
    "                temp=nums[found]\n",
    "                nums[found]=nums[the_loc-1]\n",
    "                nums[the_loc-1]=temp\n",
    "                print(nums)\n",
    "                \n",
    "                left=the_loc\n",
    "                while(left<len(nums)-1 and nums[left]<nums[left+1]):\n",
    "                    left+=1\n",
    "                right=len(nums)-1\n",
    "                while(left<right):\n",
    "                    temp=nums[right]\n",
    "                    nums[right]=nums[left]\n",
    "                    nums[left]=temp\n",
    "                    left+=1\n",
    "                    right-=1\n",
    "\n",
    "        \n",
    "    def loc(self,nums):\n",
    "        i=len(nums)-1\n",
    "        while(i>0):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                return i\n",
    "            i-=1\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        lenth = len(nums)\n",
    "        if not lenth: return []\n",
    "\n",
    "        def reverse(start, end=lenth-1):\n",
    "            while start < end:\n",
    "                nums[start], nums[end] = nums[end], nums[start]\n",
    "                start += 1\n",
    "                end -= 1\n",
    "        \n",
    "        def findJustGreater(x):\n",
    "            i = lenth - 1\n",
    "            while i > 0 and nums[i] <= x:\n",
    "                i -= 1\n",
    "            return i\n",
    "            \n",
    "        j = len(nums) - 1\n",
    "        while j > 0 and nums[j] <= nums[j-1]:\n",
    "            j -= 1\n",
    "        if j > 0:\n",
    "            i = findJustGreater(nums[j-1])\n",
    "            nums[j-1], nums[i] = nums[i], nums[j-1]\n",
    "        reverse(j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        i = j = k = len(nums) - 1\n",
    "        if i < 1:\n",
    "            return\n",
    "        while i>0 and nums[i]<=nums[i-1]:\n",
    "            i -= 1\n",
    "        i -= 1\n",
    "        while j>i>=0 and nums[j]<=nums[i]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        i += 1\n",
    "        while k > i:\n",
    "            nums[k], nums[i] = nums[i], nums[k]\n",
    "            k -= 1\n",
    "            i += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if len(nums) <= 1:\n",
    "            return \n",
    "        partition = -1\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            if nums[i] < nums[i + 1]:\n",
    "                partition = i\n",
    "                break\n",
    "        if partition == -1:\n",
    "            nums.reverse()\n",
    "            return \n",
    "        else:\n",
    "            for i in range(len(nums) - 1, partition, -1):\n",
    "                if nums[i] > nums[partition]:\n",
    "                    nums[i], nums[partition] = nums[partition], nums[i]\n",
    "                    break\n",
    "        nums[partition+1:len(nums)] = nums[partition+1:len(nums)][::-1]\n",
    "        return \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        numCount = len(nums)\n",
    "        i = numCount - 1\n",
    "        while i > 0:\n",
    "            if nums[i] > nums[i-1]:\n",
    "                break\n",
    "            i -= 1\n",
    "        if i == 0:\n",
    "            nums.sort()\n",
    "        else:\n",
    "            nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "            left, right = nums[i-1], nums[i]\n",
    "            self.quickSort(nums, i, numCount - 1)\n",
    "            basePos = i - 1\n",
    "            while i < numCount:\n",
    "                if nums[i] > right and nums[i] < left:\n",
    "                    nums[i], nums[basePos] = nums[basePos], nums[i]\n",
    "                    while i < numCount - 1:\n",
    "                        nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "                        i += 1\n",
    "                    break\n",
    "                i += 1\n",
    "\n",
    "    def median3(self, L, a, b, c):\n",
    "        if L[a] >= L[b] and L[b] >= L[c]:\n",
    "            mid = L[b]\n",
    "            i = b\n",
    "        elif L[a] <= L[b] and L[b] <= L[c]:\n",
    "            mid = L[b]\n",
    "            i = b\n",
    "        elif L[b] >= L[a] and L[a] >= L[c]:\n",
    "            mid = L[a]\n",
    "            i = a\n",
    "        elif L[b] <= L[a] and L[a] <= L[c]:\n",
    "            mid = L[a]\n",
    "            i = a\n",
    "        else:\n",
    "            mid = L[c]\n",
    "            i = c\n",
    "        return [mid,i]  \n",
    "\n",
    "    def quickSort(self, L, low, high):\n",
    "        if low < high:\n",
    "            i = low\n",
    "            j = high\n",
    "            meta = self.median3(L, i, int((i+j)/2), j)\n",
    "            pivot = meta[0]\n",
    "            pivotPos = meta[1]\n",
    "            # move pivot to the right end\n",
    "            L[pivotPos], L[high] = L[high], L[pivotPos]\n",
    "            \n",
    "            while i < j:\n",
    "                # pivot on the right end, starting from left\n",
    "                while i < j and L[i] <= pivot:\n",
    "                    i = i+1\n",
    "                while j > i and L[j] >= pivot:\n",
    "                    j = j-1\n",
    "                L[i], L[j] = L[j], L[i]\n",
    "            # move pivot to right position\n",
    "            L[i], L[high] = L[high], L[i]\n",
    "            \n",
    "            self.quickSort(L, low, i-1)\n",
    "            self.quickSort(L, i+1, high)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: 'List[int]') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        i = n - 2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i >= 0:\n",
    "            j = n - 1\n",
    "            while j >= 0 and nums[j] <= nums[i]:\n",
    "                j -= 1\n",
    "            tmp = nums[j]\n",
    "            nums[j] = nums[i]\n",
    "            nums[i] = tmp\n",
    "            \n",
    "        nums[i + 1: n] = list(reversed(nums[i + 1: n]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        cur = len(nums) - 2\n",
    "        while cur >= 0:\n",
    "            if nums[cur] < nums[cur + 1]:break\n",
    "            cur -= 1\n",
    "        if cur == -1: nums.sort()\n",
    "        else:\n",
    "            index = len(nums) -1\n",
    "            while index > cur:\n",
    "                if nums[index] > nums[cur]:\n",
    "                    nums[cur], nums[index] = nums[index], nums[cur]\n",
    "                    nums[cur + 1:] =  sorted(nums[cur + 1:])\n",
    "                    break\n",
    "                index -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        def reverse(nums, start, end):\n",
    "            while start < end:\n",
    "                temp = nums[start]\n",
    "                nums[start] = nums[end]\n",
    "                nums[end] = temp\n",
    "                start += 1\n",
    "                end -= 1\n",
    "        start = 0\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if nums[i] > nums[i-1]:\n",
    "                start = i\n",
    "                for j in range(n-1, i-1, -1):\n",
    "                    if nums[j] > nums[i-1]:\n",
    "                        temp = nums[i-1]\n",
    "                        nums[i-1] = nums[j]\n",
    "                        nums[j] = temp\n",
    "                        break\n",
    "                break\n",
    "                \n",
    "        end = n-1\n",
    "        reverse(nums, start, end)\n",
    "        return nums\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        flag = 0  # 标记是否存在下一个排列\n",
    "        for i in range(len(nums)-1, 0, -1):\n",
    "            # nums[i] > nums[i-1]时，存在下一个排列\n",
    "            if nums[i] > nums[i-1]:\n",
    "                flag = 1  \n",
    "                #取nums得i索引之后的元素，并排序\n",
    "                s = sorted(nums[i:len(nums)])\n",
    "                if len(s)>0:\n",
    "                    #生成满足大于i-1元素的列表，并取最小的，求所在nums中的位置，让这个元素和i-1元素交换位置\n",
    "                    ss = [j for j in s if j>nums[i-1]][0]\n",
    "                    c = nums.index(ss,i)\n",
    "                    \n",
    "                    nums[i-1],nums[c] = nums[c],nums[i-1]\n",
    "                    #交换完成后，i-1位置之后的元素都应该是递减的\n",
    "                    nums[i:] = sorted(nums[i:])\n",
    "                    \n",
    "                    return nums\n",
    "                else:#仅仅是最后两个元素交换位置\n",
    "                    nums[i - 1], nums[i] = nums[i], nums[i - 1]\n",
    "                    return nums\n",
    "\n",
    "        if flag == 0:  # 不存在下一个排列\n",
    "            nums.sort()\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        i = n-1\n",
    "        while i-1>=0 and nums[i]<=nums[i-1]:\n",
    "            i -= 1\n",
    "            \n",
    "        if i-1 < 0:\n",
    "            self.reverse(nums,0,n-1)\n",
    "        else:\n",
    "            x = i-1\n",
    "            while i<n and nums[i]>nums[x]:\n",
    "                i += 1\n",
    "            nums[x],nums[i-1] = nums[i-1],nums[x]\n",
    "            self.reverse(nums,x+1,n-1)\n",
    "            #nums[x+1:] = sorted(nums[x+1:])\n",
    "    def reverse(self,nums,i,j):\n",
    "        while i<j:\n",
    "            nums[i],nums[j] = nums[j],nums[i]\n",
    "            i += 1\n",
    "            j -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return None\n",
    "        index1 = -1\n",
    "        for i in range(len(nums)-1, 0,-1):\n",
    "            if nums[i-1] < nums[i]:\n",
    "                index1 = i-1\n",
    "                break\n",
    "        if index1 == -1:\n",
    "            nums[:] = nums[::-1]\n",
    "            return \n",
    "       \n",
    "        for i in range(index1, len(nums)-1):\n",
    "            if nums[i+1] <= nums[index1] < nums[i]:\n",
    "                break\n",
    "            index2 = i+1\n",
    "            \n",
    "\n",
    "        nums[index1], nums[index2] = nums[index2], nums[index1]\n",
    "        nums[index1+1:]= nums[-1:index1:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        max_i = -1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] < nums[i+1]:\n",
    "                max_i = i\n",
    "        if max_i >= 0:\n",
    "            min_above = 0\n",
    "            for i in range(n):\n",
    "                if nums[i] > nums[min_above]:\n",
    "                    min_above = i\n",
    "            for i in range(max_i+1,n):\n",
    "                if nums[i] > nums[max_i] and nums[i]<=nums[min_above]:\n",
    "                    min_above = i\n",
    "            print(nums,min_above,max_i)\n",
    "            nums[max_i], nums[min_above] = nums[min_above], nums[max_i]\n",
    "            # nums[max_i+1:] = sorted(nums[max_i+1:])\n",
    "            left, right = max_i + 1, n - 1\n",
    "            while left < right:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            print(nums)\n",
    "        else:\n",
    "            nums.sort()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        max_i = -1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] < nums[i+1]:\n",
    "                max_i = i\n",
    "        if max_i == -1:\n",
    "            nums.sort()\n",
    "            return\n",
    "        for i in range(max_i+1,n):\n",
    "            if nums[i] > nums[max_i]:\n",
    "                max_j = i\n",
    "        nums[max_i], nums[max_j] = nums[max_j], nums[max_i]\n",
    "        left = max_i+1\n",
    "        right = n-1\n",
    "        while left<right:\n",
    "            nums[left],nums[right] = nums[right],nums[left]\n",
    "            left+=1\n",
    "            right-=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        m = 0\n",
    "        n = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "        for i in range(length-2, -1, -1):\n",
    "            if nums[i] < nums[i+1]:\n",
    "                m = i\n",
    "                break\n",
    "        ##print(m)\n",
    "        for j in range(length-1, -1, -1):\n",
    "            if nums[i] < nums[j]:\n",
    "                n = j\n",
    "                break\n",
    "        ##print(n)\n",
    "        if m < n:\n",
    "            nums[m], nums[n] = nums[n], nums[m]\n",
    "\n",
    "\n",
    "            temp = nums[-1:-(length-m):-1] \n",
    "            nums[m+1::] = temp\n",
    "            \n",
    "        else:\n",
    "            temp = nums[::-1]\n",
    "            nums[:] = temp\n",
    "        print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        from sortedcontainers import SortedList\n",
    "        tail = SortedList()\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            x = tail.bisect_right(nums[i])\n",
    "            if x < len(tail):\n",
    "                v = nums[i]\n",
    "                nums[i] = tail.pop(x)\n",
    "                tail.add(v)\n",
    "                nums[i + 1: ] = tail\n",
    "                return\n",
    "            else:\n",
    "                tail.add(nums[i])\n",
    "        nums[:] = tail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums_len =len(nums)\n",
    "        for i in range(nums_len-1,0,-1):\n",
    "            print(\"i:\",i)\n",
    "            index = -1\n",
    "            for _ in range(i,nums_len):\n",
    "                print(\"_:\",_)                \n",
    "                if index<0:\n",
    "                    if nums[_]> nums[i-1]:\n",
    "                        index = _\n",
    "                else:\n",
    "                    if nums[_]>nums[i-1] and nums[_]<nums[index]:\n",
    "                        index = _\n",
    "            if index >=0:        \n",
    "                temp = nums[index]\n",
    "                nums[index] = nums[i-1]\n",
    "                nums[i-1] =temp\n",
    "                b = nums[i:]\n",
    "                b.sort()\n",
    "                nums[i:] = b\n",
    "                return\n",
    "        nums.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        len_n = len(nums)\n",
    "        if (len_n < 2):\n",
    "            return nums\n",
    "                \n",
    "        inc_idx = -1\n",
    "        swap_idx = 0\n",
    "        for i in range(len_n - 1):\n",
    "            if (nums[i + 1] - nums[i] > 0):\n",
    "                inc_idx = i\n",
    "                swap_idx = i + 1\n",
    "            else:\n",
    "                if (inc_idx >= 0 and nums[inc_idx] < nums[i + 1] < nums[swap_idx]):\n",
    "                    swap_idx = i + 1\n",
    "                    \n",
    "        if (inc_idx < 0):\n",
    "            nums.reverse()\n",
    "        else:\n",
    "            nums[inc_idx], nums[swap_idx] = nums[swap_idx], nums[inc_idx]\n",
    "            nums[inc_idx + 1:] = sorted(nums[inc_idx + 1:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        i = l - 2\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        j = l - 1\n",
    "        while j > i and nums[j] <= nums[i]:\n",
    "            j -= 1\n",
    "        if i != -1:\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        left, right = i+1, l-1\n",
    "        while left < right:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        for i in range(length - 2, -1, -1): # 从倒数第二个开始\n",
    "            if nums[i]>=nums[i+1]: continue # 剪枝去重\n",
    "            for j in range(length - 1, i, -1):\n",
    "                if nums[j] > nums[i]:\n",
    "                    nums[j], nums[i] = nums[i], nums[j]\n",
    "                    self.reverse(nums, i + 1, length - 1)\n",
    "                    return  \n",
    "        self.reverse(nums, 0, length - 1)\n",
    "    \n",
    "    def reverse(self, nums: List[int], left: int, right: int) -> None:\n",
    "        while left < right:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        i=len(nums)-1\n",
    "        sign=True\n",
    "        while i>=1:\n",
    "            if nums[i]>nums[i-1]:\n",
    "                sign=False\n",
    "                m=[nums[k] for k in range(i,len(nums)) if nums[k]>nums[i-1]]\n",
    "                idx=nums.index(min(m),i)\n",
    "                nums[idx],nums[i-1]=nums[i-1],nums[idx]\n",
    "                for l in range(len(nums)-i-1):\n",
    "                    for j in range(i,len(nums)-1):\n",
    "                        if nums[j]>nums[j+1]:\n",
    "                            nums[j],nums[j+1]=nums[j+1],nums[j]\n",
    "                break\n",
    "            else:\n",
    "                i-=1\n",
    "        if sign:\n",
    "            nums.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\r\n",
    "        \"\"\"\r\n",
    "        Do not return anything, modify nums in-place instead.\r\n",
    "        \"\"\"\r\n",
    "        if len(nums) == 2:\r\n",
    "            nums[0], nums[1] = nums[1], nums[0]\r\n",
    "        if len(nums) > 2:\r\n",
    "            stack = [nums.pop()]\r\n",
    "            while nums and nums[-1]>=stack[-1]:\r\n",
    "                stack.append(nums.pop())\r\n",
    "            if nums:\r\n",
    "                index = 0\r\n",
    "                value = nums.pop()\r\n",
    "                for i, num in enumerate(stack):\r\n",
    "                    if num > value:\r\n",
    "                        print(i)\r\n",
    "                        index = i\r\n",
    "                        break\r\n",
    "                print(nums)\r\n",
    "                print(value)\r\n",
    "                print(index)\r\n",
    "                print(stack)\r\n",
    "                nums.append(stack[index])\r\n",
    "                stack[index] = value\r\n",
    "                nums.extend(stack)\r\n",
    "            else:\r\n",
    "                nums.extend(stack)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict, deque\n",
    "from typing import List, Optional\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "def kthNextPermutation(nums: List[int], k: int, inplace=False, prev=False) -> Optional[List[int]]:\n",
    "    \"\"\"下k个字典序的排列(可以存在重复元素)\n",
    "\n",
    "    Args:\n",
    "        nums: 原排列数组.\n",
    "        k (int): 后续第k个(`本身算第0个`)字典序的排列.\n",
    "        inplace (bool, optional): 是否原地修改. 默认为False.\n",
    "        prev (bool, optional): 使用next还是prev. 默认使用next.\n",
    "\n",
    "    Returns:\n",
    "        Optional[List[int]]: 下k个字典序的排列,如果不存在,返回None.\n",
    "    \"\"\"\n",
    "    if not nums:\n",
    "        return\n",
    "    counter = Counter([nums[-1]])\n",
    "    sl = SortedList([nums[-1]]) if not prev else SortedList([nums[-1]], key=lambda x: -x)\n",
    "\n",
    "    fac = 1\n",
    "    facPtr = 1\n",
    "    curPerm = 0\n",
    "    overlap = 1  # 重复元素的个数的乘积\n",
    "    allPerm = 1  # 后缀里的所有排列个数\n",
    "    for right in range(len(nums) - 2, -1, -1):\n",
    "        if curPerm + k < allPerm:\n",
    "            break\n",
    "        num = nums[right]\n",
    "        counter[num] += 1\n",
    "        overlap *= counter[num]\n",
    "\n",
    "        smaller = 0\n",
    "        pos = sl.bisect_left(num)\n",
    "        if pos == len(sl) or sl[pos] != num:  # set去重\n",
    "            sl.add(num)\n",
    "        for pre in sl.islice(0, pos):\n",
    "            smaller += (fac * counter[pre]) // overlap\n",
    "\n",
    "        facPtr += 1\n",
    "        fac *= facPtr\n",
    "        curPerm += smaller\n",
    "        allPerm = fac // overlap\n",
    "\n",
    "    if curPerm + k >= allPerm:\n",
    "        return\n",
    "\n",
    "    res = []\n",
    "    fac //= facPtr\n",
    "    permCount = 0\n",
    "    target = curPerm + k\n",
    "    while permCount != target:\n",
    "        for i, pre in enumerate(sl):\n",
    "            curPerm = (fac * counter[pre]) // overlap  # 以当前元素开头的排列个数\n",
    "            cand = permCount + curPerm\n",
    "            if cand <= target:\n",
    "                permCount = cand\n",
    "                continue\n",
    "            facPtr -= 1\n",
    "            fac //= facPtr\n",
    "            overlap //= counter[pre]\n",
    "            res.append(pre)\n",
    "            counter[pre] -= 1\n",
    "            if not counter[pre]:\n",
    "                sl.pop(i)\n",
    "            break\n",
    "\n",
    "    for pre in sl:\n",
    "        res += [pre] * counter[pre]\n",
    "    if inplace:\n",
    "        nums[-len(res) :] = res\n",
    "        return nums\n",
    "    return nums[: len(nums) - len(res)] + res\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        res=kthNextPermutation(nums, 1, inplace=True)\n",
    "        if res is None:\n",
    "            nums.sort()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 选择左边的一个较小数与右边的一个较大数交换，要保证较小数尽量靠右，较大数尽可能小；\n",
    "    # 交换后，较小数位置右边的数要按照升序重排\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        i = len(nums) - 2   # 因为较小数要尽可能靠右，所以从右向左遍历，而且可以确保右侧一定有比它大的数\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        # 如果i < 0说明数组是降序，即最大排列方式，返回最小即可\n",
    "        # 从右向左找比较小数大的最小的较大数\n",
    "        if i >= 0:\n",
    "            j = len(nums) - 1\n",
    "            while j >= 0 and nums[i] >= nums[j]:\n",
    "                j -= 1\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        # 重新排列成最小的方式，该区间最开始必定为降序，直接交换元素即可，因为我们最小数就是这样选出来的\n",
    "        left, right = i + 1, len(nums) - 1\n",
    "        while left < right:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        pos = len(nums)-1\n",
    "        while pos >= 0:\n",
    "            if pos-1>=0 and nums[pos-1] < nums[pos]:\n",
    "                break\n",
    "            pos -= 1\n",
    "        if pos == -1:\n",
    "            nums.reverse()\n",
    "        else:\n",
    "            tar = nums[pos-1]\n",
    "            pos2 = pos\n",
    "            while pos2 < len(nums):\n",
    "                if tar>= nums[pos2]: \n",
    "                    nums[pos-1] = nums[pos2-1]\n",
    "                    nums[pos2-1] = tar\n",
    "                    break\n",
    "                pos2 += 1\n",
    "            if pos2 == len(nums):\n",
    "                nums[pos-1] = nums[len(nums)-1]\n",
    "                nums[len(nums)-1] = tar\n",
    "            for i in range((len(nums)-pos)//2):\n",
    "                tmp = nums[pos+i]\n",
    "                nums[pos+i] = nums[len(nums)-1-i]\n",
    "                nums[len(nums)-1-i] = tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lower_bound(v: List[int], tar: int, lo: int, hi: int) -> int:\n",
    "    while lo < hi:\n",
    "        # print(lo, hi)\n",
    "        mi = (lo + hi) // 2\n",
    "        if v[mi] > tar:\n",
    "            lo = mi + 1\n",
    "        else:\n",
    "            hi = mi\n",
    "    return lo\n",
    "\n",
    "\n",
    "def find(v, tar, lo, hi):\n",
    "    for i in range(lo, hi + 1):\n",
    "        if tar < v[i]:\n",
    "            pass\n",
    "        else:\n",
    "            return i - 1\n",
    "    return hi\n",
    "\n",
    "\n",
    "def reverse(v, lo, hi):\n",
    "    while lo < hi:\n",
    "        v[lo], v[hi] = v[hi], v[lo]\n",
    "        lo += 1\n",
    "        hi -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return\n",
    "        \n",
    "        i = n - 1\n",
    "        while i > 0:\n",
    "            if nums[i-1] < nums[i]:\n",
    "                break \n",
    "            else:\n",
    "                i -= 1\n",
    "\n",
    "        if i == 0:\n",
    "            reverse(nums, 0, n - 1)\n",
    "            return\n",
    "\n",
    "        # j = find(nums, nums[i-1], i, n - 1)\n",
    "        # j = lower_bound(nums, nums[i-1], i, n - 1)\n",
    "        j = lower_bound(nums, nums[i-1], i, n) - 1\n",
    "        # if nums[i-1] == nums[j]:\n",
    "        #     j -= 1\n",
    "        # print(\"nums:\", nums)\n",
    "        # print(f\"nums[{i-1}]={nums[i-1]}\")\n",
    "        # print(f\"i={i}, j={j}\")\n",
    "        nums[i-1], nums[j] = nums[j], nums[i-1]\n",
    "        reverse(nums, i, n - 1)\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
